Next Previous Table of Contents

The Internal Representation of LInteger's

Ok, What's a LInteger Look Like?

A LInteger is represented internally as a triple consisting of:

  1. a pointer to a block of unsigned ints representing the magnitude,
  2. an int representing the sign, and
  3. an int saying how many unsigned ints are in the magnitude.

The Magnitude

The unsigned ints represent the digits of the number in a base determined by the machine precision. This base is equal to 2**(bits in an unsigned int). The digits within a given magnitude are stored in consecutive memory locations such that a digit at a lower memory address has greater significance than any digit at a higher memory address. For example, consider the 64-bit magnitude 0xfedcba9876543210. On a 32-bit machine this will be stored in memory as: 

	start memory address:   0xfedcba98
	start memory address+4: 0x76543210.
Note that 4 in the above is a byte displacement. If A is an unsigned int* pointing to the magnitude, then *A=0xfedcba98 and *(A+1)=0x76543210.

Warning: It is important that magnitudes be stored with no leading zeros. This is done to speed comparisons of magnitudes and, in fact, is necessary for the internal consistency of the library. The LInteger class provides two functions to aid with this requirement:

  1. inline int LInteger::compressable() const will return zero if the integer has no lead zeros, and non-zero otherwise.
  2. void LInteger::compress() will strip the leading zeros, if any, off the magnitude, and adjust the size of the LInteger accordingly.

The Sign

The int representing the sign of the LInteger is 0 iff the integer the LInteger represents is greater than or equal to zero. If the integer the LInteger represents is negative, the sign is 1.

Warning: It is imporant, for the internal consistency of the library, that a LInteger representing zero have sign 0 and never sign 1.

The Size

This int just tells how many digits there are in the magnitude.

Next Previous Table of Contents